10007. Подсчитать деревья

 

Вычислить количество разных корневых размеченных бинарных деревьев, состоящих из n вершин. Например, из двух вершин можно составить 4 дерева:

\begin{picture}(400,90)(50,0) \put(115,62){A} \put(75,10){B} \put(120,60){\vecto... ...}} \put(365,62){B} \put(405,10){A} \put(370,60){\vector(1,-1){40}} \end{picture}

 

Вход. Каждая строка содержит количество вершин n (1 £ n £ 300). Последняя строка содержит n = 0 и не обрабатывается.

 

Выход. Для каждого теста вывести количество разных корневых размеченных бинарных деревьев, состоящих из n вершин.

 

Пример входа

1

2

10

25

0

 

Пример выхода

1

4

60949324800

75414671852339208296275849248768000000

 

 

РЕШЕНИЕ

комбинаторика + числа Каталана

 

Анализ алгоритма

Количество неразмеченных бинарных деревьев с n вершинами равно числам Каталана

Вершинам каждого неразмеченного дерева можно поставить в соответствие метки n! способами. Таким образом, число искомых размеченных корневых бинарных деревьев равно

f(n) =  * n! =  =  = (n + 2) * (n + 3) * … * (2n)

Для вычисления результата достаточно перемножить все числа от n + 2 до 2n. Поскольку n £ 300, то следует использовать класс длинной арифметики BigInteger.

 

Реализация алгоритма

Количество тестов может быть большим,  а n £ 300. Вычислим все значения f(n) и сохраним их в массиве res[MAX].

 

#define MAX 301

BigInteger res[MAX];

 

Вычислим значения f(i) и занесем их в ячейки res[i], i = 1, 2, …, 300.

 

res[1] = BigInteger(1);

for(i = 2; i < MAX; i++)

{

  res[i] = BigInteger(1);

  for(j = i + 2; j <= 2 * i; j++) res[i] = res[i] * j;

}

 

Для каждого входного n выводим res[n].

 

while(scanf("%d",&n),n) res[n].print();

 

Java реализация

 

import java.util.*;

import java.math.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

 

    BigInteger res[] = new BigInteger[301];

    res[1] = BigInteger.ONE;

    for(int i = 2; i < 301; i++)

    {

      res[i] = BigInteger.ONE;

      for(int j = i + 2; j <= 2 * i; j++)

        res[i] = res[i].multiply(BigInteger.valueOf(j));

    }

 

    while(con.hasNextInt())

    {

      int n = con.nextInt();

      if (n == 0) break;

      System.out.println(res[n]); 

    }

    con.close();

  }

}